Complementary Graphs for Connected Graphs
Title needs improvement
If a graph G with 3 or more vertices is disconnected, then for any vertex a, there is some disconnected vertex b (since if there is not, it contradicts that the graph is disconnected).
At this time, for any vertex c, which is neither a nor b, there can be no edge of both ac and bc in G (since if there were, a and b would be connected via c).
Given a complementary graph H, edge ab is contained in H and either ac or bc is contained in H, so abc is connected
---
This page is auto-translated from /nishio/連結なグラフの補グラフ. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.